package com.LeetCode.List;

import org.junit.Test;

/**
 * 有序链表转二叉搜索树
 */
public class SortListToBST {

    public TreeNode sortedListToBST(ListNode head) {
        if(head == null) return null;
        if(head.next == null) return new TreeNode(head.val);
        ListNode fast = head;
        ListNode slow = head;
        ListNode pre = slow; // 保存慢指针前一个节点

        while(fast != null && fast.next != null){
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }

        TreeNode root = new TreeNode(slow.val);

        pre.next = null;//切断链表

        root.left = sortedListToBST(head);
        root.right = sortedListToBST(slow.next);

        return root;
    }

    int len;

    ListNode h;

    public TreeNode sortedListToBST2(ListNode head){
        if(head == null) return null;
        this.len = 0;
        this.h = head;
        while(head!=null){
            len++;
            head = head.next;
        }

        return InOrderBuildBST(0, len - 1);
    }

    public TreeNode InOrderBuildBST(int start , int end){
        if(start > end) return null;
        int mid = (start + end) >>> 1;

        TreeNode left = InOrderBuildBST(start,mid-1);

        TreeNode root = new TreeNode(h.val);

        h = h.next;
        root.left = left;

        root.right = InOrderBuildBST(mid + 1, end);

        return root;
    }


    @Test
    public void test(){
        ListNode node1 = new ListNode(-10);
        ListNode node2 = new ListNode(-3);
        ListNode node3 = new ListNode(0);
        ListNode node4 = new ListNode(5);
        ListNode node5 = new ListNode(9);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        TreeNode.outTree(sortedListToBST2(node1));
    }
}
